package com.njupt.Array;

import java.util.Arrays;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 */
public class BinarySearchRange {

    /**
     * 二分查找，找到该值的时候寻找边界值
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1 ;
        int middle = -1;
        int start = -1;
        int end = -1;
        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;

        if(nums.length==0){
            return result;
        }


        while(left<=right){
            middle = (left + right) / 2;
            if(nums[middle] == target){

                start = middle;
                end = middle;
                while(start - 1 >= 0 && nums[start-1] == target){ // 防止数组越界  ！！！值得学习
                    start--;
                }
                while(end + 1 < nums.length && nums[end+1] == target){  //防止数组越界
                    end++;
                }
                result[0] = start;
                result[1] = end;
                return result;
                //查找其实位置的逻辑
            } else if (target>nums[middle]) {
                left = middle +1;
            }else {
                right = middle -1;
            }
        }
        return  result;
    }

    public int[] searchRange1(int[] nums, int target) {
        int leftBroder = leftBroder(nums,target);
        int rightBroder = rightBorder(nums,target);

        if(leftBroder == -2 || rightBroder == -2){
            return new int[]{-1,-1};
        }

        if(rightBroder-leftBroder >1){
            return new int[]{leftBroder+1,rightBroder-1};
        }

        return new int[]{-1,-1};
    }

    /**
     * 查找右边界
     * @param nums
     * @param target
     * @return
     */
    public int rightBorder(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int righterBorder = -2;
        int middle = -1;
        while(left<=right){
            middle = (left + right) / 2;
            if(target < nums[middle]){
                right = middle -1;
            }else {
                left = middle + 1;
                righterBorder = left;
            }
        }
        return righterBorder;
    }

    /**
     * 寻找左边界
     * @param nums
     * @param target
     * @return
     */
    public int leftBroder(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int middle = -1;
        int leftBorder = -2;
        while(left<=right){
            middle = (left + right) / 2;
            if(target>nums[middle]){
                left = middle + 1;
            }else {
                right = middle - 1;
                leftBorder = right;
            }
        }
        return leftBorder;
    }



    public static void main(String[] args) {
        int[] nums = {1};
        BinarySearchRange test = new BinarySearchRange();
        System.out.println(Arrays.toString(test.searchRange1(nums, 1)));

    }
}
